Last week, English, what's going to start in German, last week we talked about informed

search strategies and remember that before we talked about uninformed search strategies.

Uninformed meaning that the searching agent has only the description of the problem at

his or her its disposal. For Romania that means you have a list, unordered list of connections

possibly with costs and you have states which you cannot look into. Informed search strategies

are essentially when we have additional information. Again for Romania that might be the straight

line distance to Bucharest or something like this or a sense of smell or whatever you can

dream up. Okay so that's the difference and the upshot of what we did last week was that

heuristics can help dramatically and the end result of what we were doing was a star search

that given an admissible heuristic guarantees us optimal results and if the heuristic is

good, fast. If the heuristic is bad for instance the constant zero heuristic we're back to

uninformed search. If there's no information in the heuristic then we shouldn't be surprised

that we're not gaining anything. But for many many problems we know very good heuristics

and in those things heuristics are a game changer. For instance straight line distance is an

extremely good heuristics. For games as we'll see we have good evaluation functions where

you in chess you count your pieces right. A pawn is one, a rook is three maybe or seven

I don't know I don't remember those numbers. But you can kind of look at your board and

see how good it is at the moment. And those kind of heuristics are things we have for

many problem sets. And so we looked at how does search actually work with heuristics

on Thursday and the first thing we looked at is greedy search which is kind of the simplest

most thing you can do. Always go where your nose tells you to directly. Turns out that

has problems. It can get stuck in loops and even though it's very fast it's essentially

something like that first search you can you're not always getting optimal solutions. Okay

so greedy search uses an evaluation function which we call heuristic and that actually

is essentially an approximation or an estimation of the costs we still have to cover to the

goal. And that's something completely different than the backwards cost function we had in

uniform cost search. So we're looking forward. And as opposed to uniform cost search where

we actually know what the costs we've incurred are we can just collect them up. We don't

know what the costs to the goal are we have to estimate them but that exactly that is

the heuristic. Here is a heuristic we looked at for informed travel in Romania which is

really a heuristic I'm sure all of you are using when you see the map because you can

kind of gauge the you can gauge the straight line distance right and you would never actually

when you want to go to Bucharest you would never go there because the best way is in

the right direction to minimize the straight line distance. And you're using your experiences

with three dimensional space to do that. And one of the things is that if you go in the

right direction then you minimize straight line distance. It's even stronger you minimize

straight line distance if and only if you go into the right direction. And so your heuristic

really is go somewhere where the angle to the the angle to the to where you want to

go is smallest okay just the consequence of straight line distance. And we looked at greedy

search in Romania and it gets us to Bucharest very fast. And we kind of did the same thing

with another example. And we looked at greedy search which essentially has really bad worst

case behavior which only shows us one thing that worst case behavior isn't everything.

Worst case complexity tells us about the worst case which means no information so we can't

expect any anything better. What we really would like to do is average case complexity

but that's really hard to do. Nobody really knows how to do that. You can kind of do it

with benchmarking but you can't really do it theoretically unless you have a lot of

statistics on what you're searching for when and then it's very difficult. Okay so this

doesn't actually tell us the whole story. The only interesting things here are completeness

and optimality and completeness is wrong because we have cases like this if you want to go

from Nempt to Oradea you get caught in the chicken loop here. Okay you'll go back and